The present invention generally relates to a technique for automatically determining placement information for electronic circuit elements or the like. More particularly, the present invention relates to a technique for producing, from a given netlist, placement information for schematic circuit diagrams which may be read and/or edited by a human.
Generally speaking, a netlist provides information concerning the number and types of elements in a circuit and the manner in which they are interconnected. For example, a netlist might include a list of circuit element terminals connected on a common net. Thus, if a first AND gate receives one input from an inverter and a second input from an OR gate, and provides an output to both a NOR gate and a second AND gate, the netlist would indicate that a first net includes the inverter and the first AND gate. A second net would include the OR gate and the first AND gate. Finally, a third net would include the first AND gate, the NOR gate, and the second AND gate. It should be understood, however, that netlists are not restricted to use in describing logic diagrams. In a netlist, the interconnected circuit elements, typically referred to as cells, may be as simple as a resistor, or as complex as a microprocessor.
Netlists may be generated in a variety of ways. One common manner in which a netlist is produced is as a result of logic synthesis generation. Stated briefly, a logic synthesis tool may receive as an input a Boolean function expressed in terms of a state table, and generate a netlist including the logic circuits and the interconnections which would implement the given Boolean function.
A netlist could also be produced as an output from a typical datapath compiler. A datapath compiler will usually receive a high level schematic as an input, and produce a netlist output providing more detailed circuit information. For example, a high level schematic may include a datapath element such as a carry-save array multiplier. The datapath compiler may produce a standard netlist representing a carry-save array multiplier cell taken from a library of such cells, which standard netlist would be incorporated into the netlist of the overall circuit.
Although a netlist provides detailed interconnection information, there is no cell placement information in a netlist. As far as the netlist is concerned, two interconnected cells may be immediately adjacent with one another, or may be separated physically by hundreds or even thousands of other cells.
Techniques are known for determining cell placement based upon a given netlist. These techniques, disclosed for example in U.S. Pat. No. 3,617,714 to Kernighan et al. and in an article by C.M. Fiduccia et al., "A Linear-Time Heuristic For Improving Network Partitions," Proceedings of the 19th ACM Design Automation Conference (1982), generally relate to optimized circuit layout for a physical support such as a printed circuit board or a semiconductor substrate. However, a layout optimized for a physical support usually bears little resemblance to a schematic diagram suitable for human comprehension.
It is often desirable to provide a human-readable schematic circuit diagram of a circuit represented by a netlist. Such a schematic circuit diagram permits circuit designers to comprehend the circuit design and, if necessary, edit the design to correct errors or optimize operating efficiency. Accordingly, it is an object of the present invention to provide a technique for producing placement information for human-readable schematic circuit layouts from a given netlist.